/*
 * 1228. 链表的中点
 * 找链表的中点。
 * 
 * 
 * 样例
 * 链表 1->2->3 的中点是 2。
 * 链表 1->2 的中点是 1。
 * 
 * 挑战
 * 如果链表是一个数据流，你可以不重新遍历链表的情况下得到中点么？
 * 
 * 2018.06.09 @jeyming
 */
package middle_of_linked_list_1225;

//Definition for ListNode
class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}

public class Middle_of_linked_list_1225 {

	/*
	 * @param head: the head of linked list.
	 * @return: a middle node of the linked list
	 */
	public ListNode middleNode(ListNode head) {
		// write your code here
		int cnt = 0;
		ListNode q = head;
		while(q != null){
			++cnt;
			q = q.next;
		}
		ListNode p = new ListNode(0);
		p.next = head;
		if(cnt % 2 == 0){
			for(int i = 0; i < (cnt / 2); ++i){
				p = p.next;
			}
		} else {
			for(int i = 0; i < ((cnt+1) / 2); ++i){
				p = p.next;
			}
		}
		if(head != null)
			return p;
		else
			return null;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
